/*
 * GeneticForest.cpp
 *
 *  Created on: 24.06.2012
 *      Author: ignacio
 */

#include "GeneticForest.h"
#include "algorithm"
using std::find;
#include <set>
using std::set;
using std::pair;
//#include <iostream>
//using std::cout;
//using std::endl;

namespace neurignacio{
list<int> GenTree::getNumberLeaf() const
{
	list<int> l;
	inorderNumberLeaf(this->root,&l);
	return l;
}

void GenTree::inorderNumberLeaf(Node* x, list<int>* l) const
{
    if (x!=this->nil)
    {
    	inorderNumberLeaf(x->left,l);
    	NumberNode* n=dynamic_cast<NumberNode*>(x);
    	if (n)
    		l->push_back(*n->number);
        inorderNumberLeaf(x->right,l);
    }
}

bool GenTree::hasRepetitions() const
{
	set<int> numberSet;
	pair< set<int>::iterator, bool> ret;
	bool repetition=true;
	list<int> listOfLeaf = this->getNumberLeaf();
	list<int>::iterator it=listOfLeaf.begin();
	while (it!=listOfLeaf.end())
	{
		ret = numberSet.insert(*it);
		repetition = repetition && ret.second;
		++it;
	}
	// repetition = true => all the insertions were successful because there were no repetitions
	// repetition = false => at least one insertion failed because it was repeated
	return !repetition; // true => at least one insertion failed because it was repeated
}

void Forest::init()
{
	OPERATORPOINTERCONTAINER[0]=&ADDITION;
	OPERATORPOINTERCONTAINER[1]=&SUBSTRACTION;
	OPERATORPOINTERCONTAINER[2]=&MULTIPLICATION;
	OPERATORPOINTERCONTAINER[3]=&DIVISION;
}

void Forest::print()
{
	for (GenTreeContainer_t::iterator tree=treeContainer.begin(); tree!=treeContainer.end(); ++tree)
	{
		tree->print(); cout << " ";

	}
}

NumberNode* Forest::newNumberNode(const int& value)
{
	NumberPointer numberPointer=&(*find(NUMBERCONTAINER.begin(), NUMBERCONTAINER.end(),value));
	return newNumberNode(numberPointer);
}

NumberNode* Forest::newNumberNode(NumberPointer num)
{
	this->numberNodeContainer.push_back(NumberNode(num));
	NumberNode* z;
	z=&numberNodeContainer.back();
	z->p=Tree::nil;
	z->left=Tree::nil;
	z->right=Tree::nil;
	return z;
}
NumberNode* Forest::newRandomNumberNode()
{
	unsigned int randomInt = rand() % NUMBERCONTAINER.size();
	cout << "Forest::newRandomNumberNode(); randomInt=" << randomInt << " LINE " << __LINE__ << endl;
	return newNumberNode(&NUMBERCONTAINER[randomInt]);
}

OperatorNode* Forest::newOperatorNode(const unsigned int index)
{
	OperatorPointer op=OPERATORPOINTERCONTAINER[index];
	return newOperatorNode(op);
}
OperatorNode* Forest::newOperatorNode(OperatorPointer op)
{
	operatorNodeContainer.push_back(OperatorNode(op));
	OperatorNode* z;
	z=&operatorNodeContainer.back();
	z->p=Tree::nil;
	z->left=Tree::nil;
	z->right=Tree::nil;
	return z;
}
OperatorNode* Forest::newRandomOperatorNode()
{
	unsigned int randomInt = rand() % OPERATORPOINTERCONTAINER.size();
	return newOperatorNode(randomInt);
}
GenTree& Forest::createRandomTree()
{
	// 0. push a new tree in the container
	treeContainer.push_back(GenTree());
	GenTree& tree=treeContainer.back();
	// 1. I will create the root, this is always a operator node
	OperatorNode* op=newRandomOperatorNode();
	tree.setRoot(op);
	// 2. Create children of different values
	NumberNode* z;
	size_t numberContainerSize=NUMBERCONTAINER.size();
	//	Chose random number for left and right
	unsigned int randomIndex_right=rand() % numberContainerSize;
	unsigned int randomIndex_left;
	do
	{
		randomIndex_left=rand() % numberContainerSize;
	}
	while (randomIndex_left==randomIndex_right);
	// Create left child
	z = newNumberNode(&NUMBERCONTAINER[randomIndex_left]);
	z->p=tree.root;
	tree.root->left=z;
	// Create right child
	z=newNumberNode(&NUMBERCONTAINER[randomIndex_right]);
	z->p=tree.root;
	tree.root->right=z;
	return tree;
}

void Forest::initiate()
{
	// Clear all containers
	operatorNodeContainer.clear();
	numberNodeContainer.clear();
	treeContainer.clear();
	//
	NumberContainer_t shuffleContainer=NUMBERCONTAINER;
	random_shuffle(shuffleContainer.begin(), shuffleContainer.end());
	int numberContainerSize=shuffleContainer.size();
	for (int i=0;i<numberContainerSize; i+=2)
	{
		treeContainer.push_back(GenTree());
		GenTree& tree=treeContainer.back();
		// 1. Root
		OperatorNode* op=newRandomOperatorNode();
		tree.setRoot(op);
		// 2a. Root->left
		tree.root->left=newNumberNode(shuffleContainer[i]);
		tree.root->left->p=tree.root;
		// 2b. Root->right
		tree.root->right=newNumberNode(shuffleContainer[i+1]);
		tree.root->right->p=tree.root;
	}
}

GenTreeContainer_t::iterator Forest::RouletteWheelSelection(double totalScore, GenTreeContainer_t* container)
{
	double random = static_cast<double>(rand()) / RAND_MAX;	// random double between 0.0 and 1.0
	random *= totalScore; // random value between 0.0 and totalScore
	GenTreeContainer_t::iterator tree=container->begin();
	double score = getScore(*tree);
	while (random > score)
	{
		++tree;
		score += tree->score;
	}
	return tree;
}

double Forest::getScore(const GenTree& tree)
{
	if (allow_repetitions)
		return fitScore(tree.eval(), goal);
	else
		return fitScore(tree.eval()*(1-tree.hasRepetitions()), goal);// if repetitions, the tree evaluates to 0 for computation of score
}

double Forest::getPopulationScore()
{
	double totalScore=0;
	for (GenTreeContainer_t::iterator tree=treeContainer.begin(); tree!=treeContainer.end(); ++tree)
	{
		tree->score=getScore(*tree);	// Update the score of each tree
		totalScore += tree->score;
	}
	return totalScore;
}


double Forest::getBestScore()
{
	double bestScore=-1e100;
	for (GenTreeContainer_t::iterator tree=treeContainer.begin(); tree!=treeContainer.end(); ++tree)
	{
		tree->score = getScore(*tree);
		if (tree->score > bestScore)
		{
			bestScore = tree->score;
			fittest = &(*tree);
		}

	}
	return bestScore;
}

void Forest::mate()
{
	// Update the score of each tree of the population and returns the total score of the population
	double totalScore = getPopulationScore();
	// Sort population by decreasing fitness score
	GenTreeContainer_t sortedContainer=treeContainer;
	sortedContainer.sort(comparison);
	// Choose a breeding couple according to the Roulette Wheel Selection
	GenTreeContainer_t::iterator father = RouletteWheelSelection(totalScore, &sortedContainer);
	GenTreeContainer_t::iterator mother = RouletteWheelSelection(totalScore, &sortedContainer);
	while (father==mother)
	{
		mother = RouletteWheelSelection(totalScore, &sortedContainer);
	}
	// Create offspring
	GenTree& son=this->duplicate(*father);
	GenTree& daughter=this->duplicate(*mother);
	// Crossover offspring according to swap rule
	swap(son, daughter);
}

void CopyGenTree::inorderCopy(Node* x, Forest* forest)
// x: Node in 'this' tree
// loop: loop counter for debugging purposes
{
	if (x!=X->nil)
	{
		inorderCopy(x->left, forest);

		NumberNode* n=dynamic_cast<NumberNode*>(x);
		OperatorNode* op=dynamic_cast<OperatorNode*>(x);
		if (n && !op)
		{
			y=forest->newNumberNode(*n->number);
			if (X->root==x)
				Y->root=y;
		}
		else if (op && !n)
		{
			OperatorNode* newOp=forest->newOperatorNode(op->operation);
			if (yPrevious!=Y->nil)
			{
				newOp->p = yPrevious;
				yPrevious->right=newOp;
			}
			newOp->left=y;
			y->p=newOp;
			y=newOp;
			yPrevious=newOp;
			if (X->root==x)
				Y->setRoot(newOp);
		}
		else
		{
		}
		inorderCopy(x->right, forest);
		if (dynamic_cast<NumberNode*>(x))
		{
		}
		else if (dynamic_cast<OperatorNode*>(x))
		{
			yPrevious->right=y;
			y->p=yPrevious;
			y=yPrevious;
			yPrevious=y->p;
		}
		else
		{
			//	I will do nothing
		}
	}
}

GenTree& Forest::duplicate(GenTree& tree)
{
	this->treeContainer.push_back(GenTree());
	GenTree& copyTree=treeContainer.back();
	CopyGenTree copy(&tree, &copyTree);
	copy.inorderCopy(tree.root,this);
	return copyTree;
}

void swap(GenTree& X, GenTree& Y)
{
	// 1a. If we are in a NumberNode, swap from here
	// 1b. If we are not in a NumberNode, choose randomly between go left, go right or swap from here
	Node* n=0;	// Store the visited Node
	// Tree X
	Node* x=0; // Swap point of Genome X
	Tree::Child xChild=Tree::LEFT;
	n=X.root;
	OperatorNode* a=dynamic_cast<OperatorNode*>(n);
	// Here the probability of Swap Point is the same for each node
	while (a && !x)	// while we are a Operator Node and a Swap Point was not decided, go next
	{
		float probability = 1.0/X.size();
		float randomNumber = static_cast<float>(rand()) / RAND_MAX;
		if (randomNumber <= probability) // Choose this node
		{
			x=n;
			xChild=Tree::NONE;
		}
		else if (randomNumber > probability && randomNumber <= (probability+1)/2) // randomNumber is in the first half after the probability segment => probability + (1-probability)/2
		{
			// Go left
			n=n->left;
			xChild=Tree::LEFT;
		}
		else
		{
			// Go right
			n=n->right;
			xChild=Tree::RIGHT;
		}
		a=dynamic_cast<OperatorNode*>(n);
	}
	if (!x) // we are not in a NumberNode
		x=n;

	// Tree Y
	Node* y=0; // Swap point of Genome Y
	Tree::Child yChild=Tree::LEFT;
	n=Y.root;	// Store the visited Node
	a=dynamic_cast<OperatorNode*>(n);
	// Here the probability of Swap Point is the same for each node
	while (a && !y)	// while we are a Operator Node and a Swap Point was not decided, go next
	{
		float probability = 1.0/Y.size();
		float randomNumber = static_cast<float>(rand()) / RAND_MAX;
		if (randomNumber <= probability) // Choose this node
		{
			y=n;
			yChild=Tree::NONE;
		}
		else if (randomNumber > probability && randomNumber <= (probability+1)/2) // randomNumber is in the first half after the probability segment => probability + (1-probability)/2
		{
			// Go left
			n=n->left;
			yChild=Tree::LEFT;
		}
		else
		{
			// Go right
			n=n->right;
			yChild=Tree::RIGHT;
		}
		a=dynamic_cast<OperatorNode*>(n);
	}
	if (!y)
		y=n;

	// Cross-Over

	// Check Root
	// 1. Swap parents
	Node* temp=0;

	temp=x->p;
	x->p=y->p;
	y->p=temp;

	// 2. Swap Parent's child
	if (xChild==Tree::LEFT)
	{
		y->p->left=y;
	}
	else if (xChild==Tree::RIGHT)
	{
		y->p->right=y;
	}
	if (yChild==Tree::LEFT)
	{
		x->p->left=x;
	}
	else if (yChild==Tree::RIGHT)
	{
		x->p->right=x;
	}
	//
	if (x==X.root)
	{
		X.root=y;
	}
	if (y==Y.root)
		{
		Y.root=x;
		}
}

} // end namespace neurignacio



